package com.captain.leetcode;

/**
 * @author captain
 * @Des
 * @Date 2021/7/17 23:00
 */
public class 在排序数组中找到元素的第一个位置和最后一个位置34 {
    public static int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        int index = binarySearch(nums, target);
        if (index != -1) {
            int left = index;
            int right = index;
            while (true) {
                boolean f = true;
                //特殊情况
                if (left == 0 && right < nums.length - 1) {
                    if (nums[index] == nums[right + 1]) {
                        right++;
                        f = false;
                    }
                }
                if (left > 0 && right < nums.length - 1) {
                    if (nums[index] == nums[left - 1]) {
                        left--;
                        f = false;
                    }
                    if (nums[index] == nums[right + 1]) {
                        right++;
                        f = false;
                    }
                }
                if (f) {
                    break;
                }
            }
            return new int[]{left, right};
        } else {
            return new int[]{-1, -1};
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 4};
        for (int i : searchRange(arr, 4)) {
            System.out.println(i);
        }
    }

    static int binarySearch(int[] nums, int target) {
        int left = 0;
        //注意
        int right = nums.length - 1;
        // 注意
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1; // 注意
            else if (nums[mid] > target)
                right = mid - 1; // 注意
        }
        return -1;
    }


}
